// https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 二分查找法寻找重复数
// 2. 利用鸽巢原理：统计≤mid的数字个数
// 3. 如果count>mid，重复数在左半区；否则在右半区
// 4. 逐步缩小区间直到找到重复数
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    int findDuplicate(vector<int>& nums) 
    {
        int m = nums.size();

        int l = 1, r = m - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;

            int count = 0;
            for (int i = 0 ; i < m ; i++)
            {
                if (nums[i] <= mid)
                {
                    count++;
                }
            }

            if (count > mid)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }

        return r;
    }
};

int main()
{
    vector<int> nums1 = {1,3,4,2,2}, nums2 = {3,1,3,4,2};
    Solution sol;

    cout << sol.findDuplicate(nums1) << endl;
    cout << sol.findDuplicate(nums2) << endl;

    return 0;
}